|
In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also maintains a partition into disjoint sets but in which the operations merge pairs of sets together. More specifically, a partition refinement algorithm maintains a family of disjoint sets ; at the start of the algorithm, this is just a single set containing all the elements in the data structure. At each step of the algorithm, a set is presented to the algorithm, and each set that contains members of is replaced by two sets, the intersection and the difference . Partition refinement forms a key component of several efficient algorithms on graphs and finite automata.〔.〕〔.〕〔.〕 ==Data structure== A partition refinement algorithm may be implemented by maintaining an object for each set that stores a collection of its elements, in a form such as a doubly linked list that allows for rapid deletion, and an object for each element that points to the set containing it. Alternatively, element identifiers may be stored in an array, ordered by the sets they belong to, and sets may be represented by start and end indices into this array.〔.〕 With either of these representations, each set should also have an instance variable that may point to a second set into which it is being split. To perform a refinement operation, loop through the elements of . For each element , find the set containing , and check whether a second set for has already been formed. If not, create the second set and add to a list of the sets that are split by the operation. Then, regardless of whether a new second set was formed, remove from and add it to the second set. In the representation in which all elements are stored in a single array, moving from one set to another may be performed by swapping with the final element of and then decrementing the end index of and the start index of the new set. Finally, after all elements of have been processed in this way, loop through , separating each current set from the second set that has been split from it, and report both of these sets as newly formed sets from the refinement operation. The time to perform the refinement operations in this way is , independent of the number of elements or the total number of sets in the data structure. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「partition refinement」の詳細全文を読む スポンサード リンク
|